Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Min Cost Climbing Stairs

Problem Statement

Given an array of integers cost, where cost[i] represents the cost of the ith step on a staircase, determine the minimum total cost to reach the top of the staircase.

It is given that once you pay the cost, you can climb the stairs by either taking one step or two steps at a time. You can start stepping either from the 0 or 1 index.

Examples

  1. Example 1:

    • Input: [2, 7, 9, 3, 1]
    • Expected Output: 10
    • Justification: The minimum cost path starts on the second step (cost=7), then jumps two steps to the fourth step (cost=3), and finally reaches the end, totaling a cost of 10.
  2. Example 2:

    • Input: [3, 2, 10, 1]
    • Expected Output: 3
    • Justification: The minimum cost path is starting on the second step (cost=2) and then jumping two steps to the last step (cost=1), totaling a cost of 3.
  3. Example 3:

    • Input: [5, 10, 5, 15, 10, 5, 20]
    • Expected Output: 25
    • Justification: The optimal path involves taking the first step (cost=5), skipping to the third step (cost=5), then to the fifth step (cost=10), and finally to the sixth step (cost=5), totaling a cost of 25.

Solution

To solve this problem, we'll employ dynamic programming, a strategy that breaks the problem down into smaller subproblems, solves each subproblem just once, and stores their solutions in an array or two variables to avoid redundant calculations. This approach is effective because it exploits the problem's overlapping subproblems and optimal substructure characteristics.

The key idea is to calculate the minimum cost to reach each step from the bottom up, considering the minimum of the two possible previous steps' costs plus the current step's cost. This method ensures that we consider all possible paths to reach a step in an efficient manner, ultimately leading to the minimum total cost to reach the top.

Step-by-step Algorithm

  1. Initialize Two Variables: Start by initializing two variables, secondLast and last, to hold the costs of the first two steps, respectively. This is because you can start climbing the stairs from either of the first two steps.

  2. Iterate Through the Array: Begin iterating from the third step (index 2 in the array) until the last step. For each step i, calculate the cost to reach that step as follows:

    • Calculate the cost to reach the current step (current) as the sum of the cost of the current step (cost[i]) and the minimum cost to reach either of the two preceding steps (Math.min(secondLast, last)).
  3. Update Variables: After calculating the cost for the current step, update secondLast to last, and last to current. This step prepares the variables for the next iteration by shifting them to represent the last two steps relative to the next position in the iteration.

  4. Return the Minimum Cost: After completing the iteration through the array, return the minimum of secondLast and last. This represents the minimum cost to reach the top of the stairs, as you can finish on either the last step or skip it if it's cheaper to do so.

Algorithm Walkthrough

Let's consider the input: [5, 10, 5, 15, 10, 5, 20]

  1. Initialization:

    • secondLast = 5 (cost to reach the first step)
    • last = 10 (cost to reach the second step)
  2. Step 1 (Index 2, Cost = 5):

    • Calculate current: current = 5 + min(5, 10) = 10
    • Update secondLast and last: secondLast = 10, last = 10
  3. Step 2 (Index 3, Cost = 15):

    • current = 15 + min(10, 10) = 25
    • Update: secondLast = 10, last = 25
  4. Step 3 (Index 4, Cost = 10):

    • current = 10 + min(10, 25) = 20
    • Update: secondLast = 25, last = 20
  5. Step 4 (Index 5, Cost = 5):

    • current = 5 + min(25, 20) = 25
    • Update: secondLast = 20, last = 25
  6. Step 5 (Index 6, Cost = 20):

    • current = 20 + min(20, 25) = 40
    • Update: secondLast = 25, last = 40
  7. Return the Minimum Cost: The minimum of secondLast and last is min(25, 40) = 25.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity : The algorithm iterates through the input array exactly once. Since the operations within each iteration (calculating the minimum of two integers and updating variables) take constant time, the total time taken scales linearly with the size of the input, denoted as n.

  • Space Complexity : Space efficiency is significantly improved by using only two variables to keep track of the costs to reach the last two steps. This approach eliminates the need for an additional array to store intermediate results. As a result, the amount of memory used does not depend on the input size, making the space complexity constant.

Min Cost Climbing Stairs (easy)
Plus One (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis